\part{初等数论}

\chapter{初等数论}

\section{素数}

\begin{itementry}
    整除\&倍数\&因子:设\(a,b\)是两个整数,且\(b\neq 0\).若存在整数\(c\)使\(a=bc\),则称\(a\)被\(b\)整除,或\(b\)整除\(a\),记为\(b\mid a\).此时称\(a\)为\(b\)的倍数,\(b\)为\(a\)的因子.若\(b\)不整除\(a\),则记为\(b\nmid a\)
\end{itementry}

\begin{itementry}
    平凡因子\&真因子:1和正整数本身被称为平凡因子,其余称为真因子
\end{itementry}

\begin{itementry}
    带余除法:设\(a,b\in\ZZ\),\(b\neq 0\),则存在唯一的整数\(q,r\),使得\(a=qb+r,0\leq r<b\).该式称为带余除法,记余数\(r\equiv a(\mod b)\)
\end{itementry}

\begin{itementry}
    整除的性质:
    \begin{theitem}
        \item \(a\mid b\wedge a\mid c\Rightarrow\forall x,y\in\ZZ,a\mid(xb+yc)\)
        \item \(a\mid b\wedge b\mid c\Rightarrow a\mid c\)
        \item \(ma\mid mb\Leftrightarrow a\mid b,m\neq 0\)
        \item \(a\mid b\wedge b\mid a\Rightarrow a=\pm b\)
        \item \(a\mid b\wedge b\neq 0\Rightarrow |a|\leq|b|\)
    \end{theitem}
\end{itementry}

\begin{itementry}
    质数/素数\&合数:若正整数\(a\)大于1且只能被1和它自己整除,则称\(a\)为素数或质数;若\(a\)大于1且不是素数,则称\(a\)为合数
\end{itementry}

\begin{itementry}
    素数和合数的性质:
    \begin{theitem}
        \item 若\(d>1,p\)为素数且\(d\mid p\),则\(d=p\)
        \item 设\(p\)是素数且\(p\mid ab\),则必有\(p\mid a\)或\(p\mid b\)
        \item 合数必有素数因子
    \end{theitem}
\end{itementry}

\begin{itementry}
    算术基本定理/唯一分解定理\&素因子分解:设\(a>1\),则\(a=p_1^{r_1}\cdots p_k^{r_k}\),其中\(p_1,\dots,p_k\)是不同的素数,\(r_1,\dots,r_k\)是正整数,且在不记顺序的情况下,该表示是唯一的,称为\(a\)的素因子分解
\end{itementry}

\begin{itementry}
    定理:有无穷多个素数
\end{itementry}

\begin{itementry}
    定理:记\(\pi(n)\)为小于等于\(n\)的素数个数,则
    \begin{align*}
        \lim_{n\to\infty}\frac{\pi(n)\ln(n)}{n}=1
    \end{align*}
\end{itementry}

\begin{itementry}
    定理:若\(a\)是和数,则\(a\)必有小于等于\(\sqrt{a}\)的真因子
\end{itementry}

\section{最大公约数与最小公倍数}

\begin{itementry}
    公因子/公约数:设\(a,b\)是两个整数,若\(d\mid a\)且\(d\mid b\),则称\(d\)为\(a\)和\(b\)的公因子(公因数)
\end{itementry}

\begin{itementry}
    最大公因子/最大公约数:两个不为0的整数的公因子中,最大的公因子称为最大公因子/最大公因数,记为\(\gcd(a,b)\)
\end{itementry}

\begin{itementry}
    公倍数:设\(a\)和\(b\)是两个整数,若\(a{\mid} m\)且\(b{\mid} m\),则称\(m\)为\(a\)和\(b\)的公倍数
\end{itementry}

\begin{itementry}
    最小公倍数:两个不为0的整数的公倍数中,最小的公倍数被称为最小公倍数,记为\(\lcm(a,b)\)
\end{itementry}

\begin{itementry}
    定理:
    \begin{theitem}
        \item \(a\mid m\wedge b\mid m\Rightarrow\lcm(a,b)\mid m\)
        \item \(d\mid a\wedge d\mid b\Rightarrow d\mid\gcd(a,b)\)
    \end{theitem}
\end{itementry}

\begin{itementry}
    定理:设\(a=qb+r(a,b,q,r\in\ZZ)\),则
    \begin{gather*}
        \gcd(a,b)=\gcd(b,r)
    \end{gather*}
\end{itementry}

\begin{itementry}
    定理:设\(a,b\)不全为0,则存在整数\(x,y\)使得
    \begin{gather*}
        \gcd(a,b)=xa+yb
    \end{gather*}
\end{itementry}

\begin{itementry}
    互素\&两两互素:若\(\gcd(a,b)=1\),则称\(a\)与\(b\)互素
    \begin{subentry}
        若\(a_1,\dots,a_n\)中的任意两数都互素,则称其两两互素
    \end{subentry}
\end{itementry}

\begin{itementry}
    定理:整数\(a\)和\(b\)互素的充要条件是存在整数\(x,y\)使得
    \begin{gather*}
        xa+yb=1
    \end{gather*}
\end{itementry}

\section{同余}

\begin{itementry}
    同余:设\(m\in\ZZ^+\),\(a,b\in\ZZ\),若\(m\mid a-b\),则称\(a\)模\(m\)同于于\(b\),或\(a\)与\(b\)模\(m\)同余,记为\(a\equiv b(\mod m)\),若\(a,b\)不同余,则记为\(a\not\equiv b(\mod m)\)
\end{itementry}

\begin{itementry}
    定理:
    \begin{align*}
        a\equiv b(\mod m)&\Leftrightarrow a\mod b=b\mod m
        &\Leftrightarrow a=b+km,k\in\ZZ
    \end{align*}
\end{itementry}

\begin{itementry}
    定理:同余具有以下性质:
    \begin{theitem}
        \item 自反性:\(a\equiv a(\mod m)\)
        \item 对称性:\(a\equiv b(\mod m)\Leftrightarrow b\equiv a(\mod m)\)
        \item 传递性:
        \begin{align*}
            a\equiv b(\mod m)\wedge b\equiv c(\mod m)\Rightarrow a\equiv c(\mod m)
        \end{align*}
    \end{theitem}
\end{itementry}

\begin{itementry}
    同余的运算:若\(a\equiv b(\mod m),c\equiv d(\mod m)\),则
    \begin{align*}
        a\pm c\equiv b\pm d(\mod m),ac\equiv bd(\mod m)\\
        a^k\equiv b^k(\mod m),k\in\ZZ^+
    \end{align*}
\end{itementry}

\begin{itementry}
    定理:
    \begin{theitem}
        \item 设\(d\geq 1\),\(d\mid m\),则\(a\equiv b(\mod m)\Rightarrow a\equiv b(\mod d)\)
        \item 设\(d\geq 1\),则\(a\equiv b(\mod m)\Leftrightarrow da\equiv db(\mod dm)\)
        \item 设\(\gcd(c,m)=1\),则\(a\equiv b(\mod m)\Leftrightarrow ca\equiv cb(\mod m)\)
    \end{theitem}
\end{itementry}

\begin{itementry}
    模等价类:整数\(a\)再模\(m\)同余关系下的等价类记为\([a]_m\),称为\(a\)的模等价类
\end{itementry}

\begin{itementry}
    一次同余方程:设\(m>0\),方程\(ax\equiv c(\mod m)\)称为一次同余方程
\end{itementry}

\begin{itementry}
    定理:一次同余方程有解的充要条件是\(\gcd(a,m)\mid c\)
\end{itementry}

\begin{itementry}
    逆:若\(ab\equiv 1(\mod m)\),则称\(b\)为\(a\)的逆,记为\(a^{-1}(\mod m)\)或\(a^{-1}\)
\end{itementry}

\section{欧拉定理和费马小定理}

\begin{itementry}
    欧拉函数:对任意正整数\(n\),把\(\{0,1,\dots,n-1\}\)中与\(n\)互素的个数记为\(\varphi(n)\),称为欧拉函数
\end{itementry}

\begin{itementry}
    欧拉定理:设\(a\)与\(n\)互素,则\(a^{\varphi(n)}\equiv 1(\mod n)\)
\end{itementry}

\begin{itementry}
    费马小定理:设\(p\)为素数,\(\gcd(a,p)=1\),则
    \begin{align*}
        a^{p-1}\equiv 1(\mod p)\text{或}a^p\equiv a(\mod p)
    \end{align*}
\end{itementry}